package Year22_Month05.day29;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 后续遍历_迭代2 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // cur 用来遍历
        TreeNode cur = root;
        // prev 用来记录上次遍历的个结点
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.add(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (cur.right != null && cur.right != prev) {
                    // 有右子树并且右子树没遍历，需放回根结点到栈中
                    stack.push(cur);
                    // 接下来遍历右子树
                    cur = cur.right;
                } else {
                    // 没有右子树，或者右子树被遍历过，
                    res.add(cur.val);
                    // 更新前指针
                    prev = cur;
                    // 以该结点的子树都已遍历，下次需要从栈中取父亲结点向上遍历，所以 cur == null
                    cur = null;
                }
            }
        }
        return res;
    }
}
